package org.hxzon.util.sort;

import java.util.Comparator;

public class QuickSort {

    public static <T> void quickSort(T objs[], Comparator<T> comp) {
        quickSort(objs, 0, objs.length - 1, comp);
    }

    public static <T> void quickSort(T objs[], int left, int right, Comparator<T> comp) {
        if (left >= right) {
            return;
        }
        int vi = median3Index(objs, left, right, (right + left) / 2, comp);
        debug(objs[left] + "," + objs[right] + "," + objs[(right + left) / 2] + ",select:" + objs[vi]);
        swap(objs, left, vi);//选择“主元”，放在第一个位置
        //
        int i = left + 1;
        int j = right;
        while (true) {
            //顺序很重要，要先从右边开始找
            while (comp.compare(objs[j], objs[left]) > 0) {
                j--;
            }
            while (comp.compare(objs[i], objs[left]) < 0) {
                i++;
            }
            if (i < j) {
                swap(objs, i, j);
                debug(objs, left, right);
                i++;
                j--;
            } else {
                break;
            }
        }
        debug(objs, left, right);
        //
        swap(objs, left, i - 1);//vi=i-1
        debug("final:");
        debug(objs, left, right);
        //
        quickSort(objs, left, i - 2, comp);//vi-1
        quickSort(objs, i, right, comp);//vi+1
    }

    //===========================
    public static <T> void quickSort2(T objs[], Comparator<T> comp) {
        quickSort2(objs, 0, objs.length - 1, comp);
    }

    public static <T> void quickSort2(T objs[], int left, int right, Comparator<T> comp) {
        if (left >= right) {
            return;
        }
        int vi = median3Index(objs, left, right, (right + left) / 2, comp);
        swap(objs, left, vi);
        //
        int i = left + 1;
        int m = left;
        for (; i <= right; i++) {
            if (comp.compare(objs[i], objs[left]) < 0) {
                swap(objs, ++m, i);
            }
        }
        swap(objs, left, m);
        quickSort2(objs, left, m - 1, comp);
        quickSort2(objs, m + 1, right, comp);
    }

    public static <T> int median3Index(T objs[], int a, int b, int c, Comparator<T> comp) {
        int bigger = comp.compare(objs[a], objs[b]) > 0 ? a : b;
        return comp.compare(objs[bigger], objs[c]) < 0 ? bigger : c;
    }

    public static <T> void swap(T a[], int i, int j) {
        T tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    public static void debug(Object objs[], int left, int right) {
        for (int i = left; i <= right; i++) {
            System.out.print(objs[i] + " ");
        }
        System.out.println();
    }

    public static void debug(Object o) {
        System.out.println(o);
    }

//算法思想：以第一个元素为准，小于该元素的放在左边，不小于该元素的放在右边，然后对两侧元素递归排序。
//快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。
//
//改进：快速排序有一个很大不足就是对于比较有序的数组排序效率很低，而且当数组较短时快速排序并不是最快的。
//应对这些情况有三种简单常用的改进：
//随机化改进：不是选取第一个值为基准，而是随机选取。
//平衡化改进：取第一个、最后一个和中间点三个值中中间值为基准进行排序。
//设置阀值--混合排序：当数组长度小于某一值时使用其他较快的排序。
//
//算法分析：
//时间代价：最好情况是O(n log n),最坏情况是O(n2)。
//如果设f(n)为数组长为n时的比较次数，则f(n)=[(f(1)+f(n-1))+(f(2)+f(n-2))+...+(f(n-1)+f(1))]/n.
//利用数学知识易知f(n)=(n+1)*[1/2+1/3+...+1/(n+1)]-2n~1.386nlog(n).
//空间代价：程序所需的空间即为堆栈深度(用于存储l,u,m)，所以空间代价为O(log(n))
//稳定性：快速排序时不稳定的，即不保序的。
//
//评价：快速排序的时间代价比较低，空间代价也比较低，算是时空代价相当好的算法。
//而且在下面的数值试验中也会发现，快速排序效率还是很好的。
//但是最大的不足使快速排序不稳定。
//比如在excel中进行排序，我们自然希望排序结果是稳定的（即相同的数排序后与原来的顺序相同）。

//错误版本1：
//    while (true) {
//        //顺序很重要，要先从右边开始找
//        //(while j>i && ...) is error
//        while (j >= left + 1 && comp.compare(objs[j], objs[left]) > 0) {
//            j--;
//        }
//        //(while i<j && ...) is error
//        //(while ... && <0) is error
//        while (i <= right && comp.compare(objs[i], objs[left]) < 0) {
//            i++;
//        }
//        if (i < j) {
//            swap(objs, i, j);
//            debug(objs, left, right);
//            i++;
//            j--;
//        }
//        if(i>=j) {//这里应改为else，否则，i++,j--后，值为比较就退出了
//            break;
//        }
//    }
//92, 10, 21, 3, 38, 5, 62, 92, 4, 12, 57, 66, 3, 4
    //92,4,62,select 62
    //[62],10,21,3,38,5,92_,92,4,12,57,66,3,4
    //[62],10,21,3,38,5,92_i,92,4,12,57,66,3,4_j
    //[62],10,21,3,38,5,4_i,92,4,12,57,66,3,92_j
    //[62],10,21,3,38,5,4,92_i,4,12,57,66,3_j,92
    //[62],10,21,3,38,5,4,3_i,4,12,57,66,92_j,92
    //[62],10,21,3,38,5,4,3,4,12,57_j,66_i,92,92
    //57_,10,21,3,38,5,4,3,4,12,[62],66,92,92
    //
    //57,12,38,select 38
    //[38],10,21,3,57_,5,4,3,4,12
    //[38],10,21,3,57_i,5,4,3,4,12_j
    //[38],10,21,3,12_i,5,4,3,4,57_j
    //[38],10,21,3,12,5,4,3,4,57_i (j=0)
    //4_,10,21,3,12,5,4,3,[38],57
    //
    //4,3,3,select 3
    //[3],10,21,4_,12,5,4,3
    //[3],10_i,21,4,12,5,4,3 (j=0)(if find cond is <=0,then 3 can change with 10)
    //[3]_,10,21,4,12,5,4,3
    //
    //10,3,12,select 10
    //[10],21,4,12,5,4,3
    //[10],21_i,4,12,5,4,3_j change
    //[10],3_i,4,12,5,4,21_j
    //[10],3,4,12_i,5,4_j,21 change
    //[10],3,4,4_i,5_ni_nj,12_j,21 stop
    //[10],3,4,4_,5_i_j,12,21
    //4_,3,4,[10],5,12,21 error here,10 now before 5
}
